Apabila Algeria mendapat kemerdekaan pada 1962, Abdelaziz menjadi timbalan menteri di Tlemcen dan Menteri Belia dan Sukan Algeria yang ketika itu Presiden Algeria ialah Ben Bella. Tahun 1963, Abdelaziz dilantik pula sebagai Menteri Luar Negeri Algeria dan menjawat tugas itu sehingga kematian Presiden Houari Boumédienne pada 1978. Beliau sangat rapat dengan Houari Boumédienne dan menjadi ahli 'Oujda clan'. Ben Bella cuba memecat Houari Boumédienne pada 1965 kerana cubaan rampasan kuasa. Tetapi dengan kuasa pada Houari Boumédienne , dia dilihat lebih berupaya dan lebih berjaya. Abdulaziz dilihat sebagai orang kanan Houari Boumédienne, lebih terbuka untuk pembaharuan ekonomi dan lebih kompromi dengan negara Barat. Sebaliknya Kolonel Mohamed Salah Yahiaoui dilihar sebagai orang kiri Maumedienne. Selepas tentera ambilalih kuasa, Abdelaziz mengundurkan diri dari menjadi menteri.